package com.LeeCode;

/**
 * 最大的幻方
 */

public class Code1895 {
    public static void main(String[] args) {

    }

    public int largestMagicSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        // 预处理前缀和
        int[][] rowPrefix = new int[m][n + 1];
        int[][] colPrefix = new int[m + 1][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowPrefix[i][j + 1] = rowPrefix[i][j] + grid[i][j];
            }
        }

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colPrefix[i + 1][j] = colPrefix[i][j] + grid[i][j];
            }
        }

        // 从大到小枚举幻方尺寸
        for (int size = Math.min(m, n); size >= 1; size--) {
            for (int i = 0; i <= m - size; i++) {
                for (int j = 0; j <= n - size; j++) {
                    if (checkMagic(grid, rowPrefix, colPrefix, i, j, size)) {
                        return size;
                    }
                }
            }
        }

        return 1;
    }

    private boolean checkMagic(int[][] grid, int[][] rowPrefix, int[][] colPrefix,
                               int row, int col, int size) {
        // 获取第一行的和作为基准
        int sum = rowPrefix[row][col + size] - rowPrefix[row][col];

        // 检查所有行
        for (int i = 0; i < size; i++) {
            int currentSum = rowPrefix[row + i][col + size] - rowPrefix[row + i][col];
            if (currentSum != sum) return false;
        }

        // 检查所有列
        for (int j = 0; j < size; j++) {
            int currentSum = colPrefix[row + size][col + j] - colPrefix[row][col + j];
            if (currentSum != sum) return false;
        }

        // 检查主对角线
        int diag1 = 0;
        for (int i = 0; i < size; i++) {
            diag1 += grid[row + i][col + i];
        }
        if (diag1 != sum) return false;

        // 检查副对角线
        int diag2 = 0;
        for (int i = 0; i < size; i++) {
            diag2 += grid[row + i][col + size - 1 - i];
        }
        if (diag2 != sum) return false;

        return true;
    }
}
